/**
 * 8大排序算法
 * <p>
 * 1.内部排序算法(直接在内存中进行)
 * 2.外部排序算法(内存和外存结合使用)
 * <p>
 * 内部排序又分为: 1.1 直接插入排序  1.2 希尔排序 1.3
 */
public class PaixuInterview {

    /**
     * 直接插入排序:在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排
     * 好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
     * 也是排好顺序的。如此反复循环，直到全部排好顺序
     *
     * @param nums
     * @return
     */
    public static void insertSort(int[] nums) {
        int temp = 0;
        for (int i = 1; i < nums.length; i++) {
            temp = nums[i];
            int j = i - 1;
            for (; j >= 0 && temp < nums[j]; j--) {
                nums[j + 1] = nums[j];
            }
            nums[j + 1] = temp;
        }

//        return nums;
        for (int i : nums) {
            System.out.println(i);
        }
    }

    public static void main(String[] args) {
        int a[] = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};
        PaixuInterview.insertSort(a);
    }
}
